//
// Created by Liming Shao on 10/30/2017.
//

#include "D181.h"
#include <iostream>

// 1 1 2 3 5 8 13 21
// 时间复杂度 O(2^N)
int D181::Fibonacci1(int N) {
    if (N <= 0)
        return 0;

    if (N == 1 || N==2)
        return 1;

    return Fibonacci1(N-1)+Fibonacci1(N-2);
}

// 时间复杂度 O(N)
int D181::Fibonacci2(int N) {
    if (N <= 0)
        return 0;

    if (N == 1 || N==2)
        return 1;

    int pre2 = 1;
    int pre1 = 1;
    int sum = 0;
    while(--N >1){
        sum = pre1 + pre2;
        pre2 = pre1;
        pre1 = sum;
    }

    return sum;
}

// 时间复杂度 O(logN)
// |F(N), F(n-1)| = |(F(N), F(n-1)| * |[[1,1], [1,0]]| ^(N-1)
// 把计算转化为求矩阵幂的方式，可以降低时间复杂度。

int D181::Fibonacci3(int N) {
    // |F(N), F(n-1)| = |(F(N), F(n-1)| * [[1,1], [1,0]]
    // |F(N), F(n-1)| = |(F(2), F(1)| * |[[1,1], [1,0]]| ^ (N-2)

    // 先求|[[1,1], [1,0]]| ^ (N-2)
    int n = N - 2;
    vector<vector<int> > matrix({{1,1},{1,0}});

    vector<vector<int> > resMatrix({{1,0},{0,1}}); // 单位矩阵
    vector<vector<int> > doubleMatrix = matrix;

    for (int i = 0; n >= (1<<i) ; ++i) {
        if ((n>>i) & 0x01){
            //resMatrix = resMatrix * doubleMatrix
            resMatrix = muliMatix(doubleMatrix, resMatrix);
        }
        // doubleMatrix = doubleMatrix * matrix
        doubleMatrix = muliMatix(doubleMatrix, doubleMatrix);
    }

    // F(N)为矩阵幂的第一列与|F(2),F(1)|的乘积，这里F(2)=F(1)=1，故为第一列之和。
    return resMatrix[0][0]+resMatrix[1][0];
}

vector<vector<int> > D181::muliMatix(vector<vector<int> > a, vector<vector<int> > b) {
    vector<vector<int> > ret(2, vector<int>(2));
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                ret[i][j] += a[i][k] * b[k][j];
    return ret;
}

// 1 2 3 5 8 11
// N个台阶组合分为 F(N-1)-1 和F(N-2)-2，故有F(N)=F(N-1)+F(N-2)
int D181::Question1(int N) {
    if (N <= 0)
        return 0;

    if (N == 1 || N==2)
        return N;

    return Question1(N-1)+Question1(N-2);
}

int D181::Question2(int N) {
    return 0;
}

void D181::test() {

    std::cout << Fibonacci1(30) << std::endl;
    std::cout << Fibonacci2(30) << std::endl;
    std::cout << Fibonacci3(30) << std::endl;
}







